1. Field of the Invention
The present invention is a novel method for selecting communication frequencies that will be used in the geographic regions in cellular communication systems.
2. Description of the Related Art
Communication systems that service wide areas are limited by the availability of radio frequencies. Given the practical constraints associated with the construction of radio equipment, a communication system is normally tailored to operate within a given range of radio frequencies. The range of radio frequencies that can be utilized is usually further constrained by international treaties and national laws that govern allocation of the frequency spectrum in general. A communication system must select a frequency range that can be accommodated by the radio equipment and satisfies the non-technical limitations. This frequency range is then partitioned into a limited number of communication channels. To obtain a capacity above the channel limit, an attempt must be made to reuse the channels.
Cellular communication systems are good examples of how a limited number of communication channels can be used again and again. The service area of a cellular communication system is partitioned into a plurality of geographic regions called cells. As the need for communication capacity increases, a single channel can be used in several different cells at one time. Channel reuse in cellular systems is still limited by factors such as inter-cell interference and equipment limitations.
Allocating the limited number of channels available in a cellular system to the various cells poses a challenge to frequency reutilization. The ultimate goal is to provide communication service within each cell, regardless of how many channels are demanded in each cell. Communication services are provided when a user terminal calls another user terminal. When a cell requires an additional channel for communication but there are no channels available, that call is said to be blocked. Every call that is blocked due is to the lack of an available communication channel results in lost revenue to the service provider.
Imprudent channel allocations can cause the call blocking rate to escalate. A cellular communication system based on a judicious method for allocating channels significantly reduces the call blocking rate over traditional channel allocation methods. Each additional call that can be completed as a result of the channel allocation strategy results in additional revenue to the service provider.
Two methods have previously been used to allocate channels to cells. The first method employs a fully static allocation, and the second a fully dynamic allocation. The fully dynamic method is known as the "Greedy Algorithm". Marginal performance improvements have been attached for fully dynamic allocation. However, each of these prior methods has significant limitations.
Cellular channel allocation using static allocation relies on the anticipated amount of communication demand in each cell in the system. Communication channels are allocated to the cells during system initialization based on the predicted demand. This most traditional method fails when any particular cell requires capacity greater than the original prediction. Once the predicted capacity in a cell is. exceeded, call blocking occurs immediately and causes lost revenue.
Fully dynamic allocation would seemingly provide virtually limitless capacity to a given cell, but this is not the case. Fully dynamic allocation allocates communication channels to the various cells as the demand for communication varies over time, but channels are allocated in a completely random fashion. A problem with this technique is a lack of foresight with which channels are allocated. As the system operates, channels are allocated to cells in anarchical fashion. When cells require additional channels, other restrictions, including channel reutilization constraints and inter-cell interference, can preclude subsequent channel assignments. This can result in blocked calls and lost revenue.
The limitations associated with fully dynamic allocation led to a recognition that, when all available channels were grouped together for allocation to the cells in the system, the assignment of a channel to a cell could occur when the channel was not used by cells located within a prescribed reuse zone. While refining the Greedy Algorithm, a technique was developed called the usefulness factor. This technique measured the likelihood that a channel would later be needed by a cell's neighbors.